 //572.另一棵树的子树
 //https://leetcode.cn/problems/subtree-of-another-tree
class Solution {
public:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if(!root || !subRoot) return false;
        function<bool(TreeNode*,TreeNode*)> dfs = [&dfs](TreeNode* r,TreeNode* sr)->bool {
            if(!r && !sr) return true;
            if(!r || !sr) return false;
            if(r->val != sr->val) return false;

            //判断当前的root和subRoot的左右子树节点是否相同
            if((r->left&&sr->left)&&(r->left->val != sr->left->val)
            || (r->right&&sr->right)&&(r->right->val != sr->right->val))
                return false;

            return dfs(r->left,sr->left) && dfs(r->right,sr->right);
        };
        if(dfs(root,subRoot)) return true;

        return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
    }
};